package 链表;

public class No92反转链表_2 {

    /**
     * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
     * 说明:
     * 1 ≤ m ≤ n ≤ 链表长度。
     * 示例:
     * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
     * 输出: 1->4->3->2->5->NULL
     */

    //根据东哥大佬的解法,先实现第一步,反转前n个链表
    private static ListNode nextList;

    public static ListNode op1(ListNode head,int n){
        if(n==1){
            nextList=head.next;//记录后驱节点
            return head;
        }
        //递归函数返回的是最后的一个翻转节点
        ListNode listNode = op1(head.next, n - 1);
        /**
         * 然后就开始自己的翻转之路,无关递归回来的listNode
         */
        head.next.next=head;//下一个节点(head.next)的指针(next)指向自己
        head.next=nextList;//本节点的指针指向后驱节点(最终只有头节点会指向)
        return listNode;
    }

    /**
     * 根据上方的启发然后开始解题,上方解题分为两部分
     * 1.逐步开始翻转
     * 2.停止翻转,记录后驱节点,返回最后一个节点
     */
    static int index=0;
    static ListNode successor ;//后驱节点
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dg = DG(head, m-1 , n-1 );
        return dg;
    }

    private static ListNode DG(ListNode head,int m,int n){
        if(index==n){
            //最后一个翻转节点了
            successor=head.next;//记录后驱节点
            return head;//返回最后一个节点
        }else if(m<=index&&index<n){
            index++;
            //开始递归返回的是最后一个节点
            ListNode listNode = DG(head.next, m, n);
            head.next.next=head;
            head.next=successor;
            return listNode;//一直返回的都是最后一个节点
        }else{
            if(index>=n)
                return head;
            index++;
            //得到上方返回的最后一个节点,接上去
            ListNode listNode = DG(head.next, m, n);
            head.next=listNode;
            return head;
        }
    }

    public static void main(String[] args) {

        ListNode listNode5=new ListNode(5,null);
        ListNode listNode4=new ListNode(4,listNode5);
        ListNode listNode3=new ListNode(3,listNode4);
        ListNode listNode2=new ListNode(2,listNode3);
        ListNode listNode1=new ListNode(1,listNode2);
//        ListNode cur = op1(listNode1, 3);

        ListNode cur=reverseBetween(listNode1,2,4);

        while (cur!=null){
            System.out.println(cur.val);
            cur=cur.next;
        }

    }


}
